package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 2470. 最小公倍数为 K 的子数组数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/14 17:18
 */
public class SubarrayLCM {

    public static void main(String[] args) {
        SubarrayLCM test = new SubarrayLCM();

        // 4
//        int[] nums = {3, 6, 2, 7, 1};
//        int k = 6;

        // 0
//        int[] nums = {3};
//        int k = 2;

        // 4
        int[] nums = {13, 2, 14, 9, 13, 1, 11, 1, 8};
        int k = 11;

        int i = test.subarrayLCM(nums, k);
        System.out.println(i);
    }

    public int subarrayLCM(int[] nums, int k) {
        int length = nums.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = (k % nums[i] == 0) ? 1 : 0;
        }
        int count = 0;
        for (int i = 0; i < length; i++) {
            int item = nums[i];
            if (item == 0) {
                continue;
            }
            if (item == k) {
                count++;
            }
            for (int j = i + 1; j < length; j++) {
                if (arr[j] == 0) {
                    break;
                }
                item = item * nums[j] / find(item, nums[j]);
                if (item > k) {
                    break;
                }
                if (item == k) {
                    count++;
                }
            }
        }
        return count;
    }

    private int find(int a, int b) {
        if (b == 0) {
            return a;
        }
        return find(b, a % b);
    }

}
